package exhaustivity.partners;

import java.util.ArrayList;
import java.util.List;

/**
 * @author longzj
 */
class GaleShapley {

    public static void main(String[] args) {
        GaleShapley shapley = new GaleShapley();
        shapley.printResult();
    }

    private void printResult() {
        List<Person> men = new ArrayList<>();
        men.add(new Person(0, new int[]{2, 0, 1, 3}));
        men.add(new Person(1, new int[]{0, 1, 3, 2}));
        men.add(new Person(2, new int[]{0, 2, 1, 3}));
        men.add(new Person(3, new int[]{3, 1, 2, 0}));

        List<Person> women = new ArrayList<>();
        women.add(new Person(0, new int[]{1, 0, 2, 3}));
        women.add(new Person(1, new int[]{0, 1, 3, 2}));
        women.add(new Person(2, new int[]{0, 2, 1, 3}));
        women.add(new Person(3, new int[]{3, 1, 2, 0}));

        match(men, women);
        for (Person man : men) {
            Person woman = women.get(man.getMatchedIndex());
            System.out.println("[" + man.getIndex() + "," + woman.getIndex() + "]");
        }

    }

    private void match(List<Person> men, List<Person> women) {
        boolean allMatched = false;
        while (!allMatched) {
            allMatched = true;
            for (Person man : men) {
                int manMatchedId = man.getMatchedIndex();
                if (manMatchedId != -1) {
                    break;
                }
                allMatched = false;
                int[] womenIndexList = man.getFavList();
                int womanLastPosition = man.getLastPosition();
                for (int index = womanLastPosition; index < womenIndexList.length; index++) {
                    Person woman = women.get(womenIndexList[index]);
                    int[] manIndexList = woman.getFavList();
                    int womanMatchId = woman.getMatchedIndex();
                    int manLastPos = woman.getLastPosition();
                    int currentManPos = getCurrentPosition(manIndexList, man.getIndex());
                    boolean changeId = false;
                    if (womanMatchId == -1) {
                        changeId = true;
                    } else if (manLastPos > currentManPos) {
                        men.get(manIndexList[manLastPos]).setMatchedIndex(-1);
                        changeId = true;
                    }
                    if (changeId) {
                        man.setMatchedIndex(woman.getIndex());
                        man.setLastPosition(index);
                        woman.setMatchedIndex(currentManPos);
                        woman.setLastPosition(currentManPos);
                        break;
                    }

                }
            }
        }
    }

    private int getCurrentPosition(int[] list, int value) {
        for (int pos = 0; pos < list.length; pos++) {
            if (list[pos] == value) {
                return pos;
            }
        }
        return -1;
    }


}
